/*
 * @lc app=leetcode.cn id=912 lang=cpp
 *
 * [912] 排序数组
 *
 * https://leetcode.cn/problems/sort-an-array/description/
 *
 * algorithms
 * Medium (55.70%)
 * Likes:    651
 * Dislikes: 0
 * Total Accepted:    431.7K
 * Total Submissions: 775K
 * Testcase Example:  '[5,2,3,1]'
 *
 * 给你一个整数数组 nums，请你将该数组升序排列。
 * 
 * 
 * 
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [5,2,3,1]
 * 输出：[1,2,3,5]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [5,1,1,2,0,0]
 * 输出：[0,0,1,1,2,5]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 <= nums.length <= 5 * 10^4
 * -5 * 10^4 <= nums[i] <= 5 * 10^4
 * 
 * .
 */

// @lc code=start

#include <vector>
#include <stdlib.h>
#include <iostream>

using namespace std;

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int size = nums.size();


        // 冒泡排序
        // bubbleSort(nums, size);

        // 选择排序
        // chooseSort(nums, size);
        
        // 插入排序
        // insertSort(nums, size);

        // 希尔排序
        // shellSort(nums, size);

        //  归并排序
        // vector<int> ans(size);
        // mergeSort(nums, 0, size-1, ans);

        // 快速排序
        // quickSort(nums, 0, size-1);

        // 堆排序
         heapSort(nums, size);

        return nums;
    }

    void heapSort(vector<int>&nums, int size)
    {
        for(int i = size / 2 - 1; i >= 0; i--) // i = ((size-1) - 1) / 2 
        {
            heapDown(nums, size, i);
        }
        for(int i = size - 1; i > 0; i--)
        {
            swap(nums[i], nums[0]);
            heapDown(nums, i, 0);
        }
    }
    void heapDown(vector<int>& nums, int size, int i)
    {
        while(i < size)
        {
            int maxIndex = i;
            int leftSon = 2 * i + 1;
            int rightSon = 2 * i + 2;
            if(leftSon < size && nums[leftSon] > nums[maxIndex]) maxIndex = leftSon;
            if(rightSon < size && nums[rightSon] > nums[maxIndex]) maxIndex = rightSon;
            if(i == maxIndex) break;
            swap(nums[i], nums[maxIndex]);
            i = maxIndex;
        }
    }

    void quickSort(vector<int>& nums, int left, int right)
    {
        if(left >= right) return;     
        int mid = quick(nums, left, right);
        quickSort(nums, left, mid-1);
        quickSort(nums, mid+1, right);
    }
    int quick(vector<int>& nums, int left, int right)
    {
        int pivot = rand() % (right - left + 1) + left;
        int temp = nums[left];
        nums[left] = nums[pivot];
        nums[pivot] = temp;
        pivot = nums[left];
        while(left < right){
            while(left < right && nums[right] >= pivot) right--;
            nums[left] = nums[right];
            while(left < right && nums[left] <= pivot) left++;
            nums[right] = nums[left]; 
        }
        nums[left] = pivot;
        return left;
    }

    void mergeSort(vector<int>& nums, int left, int right, vector<int>& ans)
    {
        if(right <= left) return;

        int mid = left + (right - left) / 2;

        mergeSort(nums, left, mid, ans);
        mergeSort(nums, mid + 1, right, ans);

        merge(nums, left, right, ans);
    }
    void merge(vector<int>& nums, int left, int right, vector<int>& ans)
    {
        int mid = left + (right - left) / 2;
        int i = left, j = mid + 1, k = 0;

        while(i <= mid && j <= right)
        {
            if(nums[i] < nums[j]) ans[k++] = nums[i++];
            else ans[k++] = nums[j++];
        }

        while(i <= mid)
        {
            ans[k++] = nums[i++];
        }

        while(j <= right)
        {
            ans[k++] = nums[j++];
        }

        for(i = left; i <= right; i++)
        {
            nums[i] = ans[i-left];
        }

    }

    void shellSort(vector<int>& nums, int size)
    {
        for(int gap = size / 2; gap > 0; gap/=2)
        {
            for(int i = gap; i < size; i++)
            {
                int minValue = nums[i];
                int j = i - gap;
                while(j >= 0 && nums[j] > minValue)
                {
                    nums[j+gap] = nums[j];
                    j -= gap;
                }
                nums[j+gap] = minValue;
            }
        }
    }

    void bubbleSort(vector<int>& nums, int size)
    {
        for(int i = 0; i < size-1; i++)
        {
            bool bFlag = false;
            for(int j = 1; j < size - i; j++)
            {
                if(nums[j-1] > nums[j]) 
                {
                    swap(nums[j], nums[j-1]);
                    bFlag = true;
                }
            }
            if(!bFlag)
                break;
        }
    }

    void chooseSort(vector<int>& nums, int size)
    {
        for(int i = 0; i < size - 1; i++)
        {
            int minIndex = i;
            for(int j = i+1; j < size; j++)
            {
                if(nums[j] < nums[minIndex]) minIndex = j;
            }
            if(minIndex != i) swap(nums[minIndex], nums[i]);
        }
    }

    void insertSort(vector<int>& nums, int size)
    {
        for(int i = 1; i < size; i++)
        {
            int minValue = nums[i];
            int j = i - 1;
            while(j >= 0 && nums[j] > minValue)
            {
                nums[j+1] = nums[j];
                j--;
            }
            nums[j+1] = minValue;
        }
    }
};


// @lc code=end

